#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

__inline unsigned int xor128(void) {
 static unsigned int
 x=123456789UL,y=362436069UL,z=521288629UL,w=88675123UL;
 unsigned int t=x^(x<<11);
 x=y; y=z; z=w; return w^=(w>>19)^t^(t>>8); }


lower_bound_sample() {
vector<unsigned int> v,w;
unsigned int n,k=0,cnt=0;
for(n=0; n<10000; n++) { k+=xor128()%8; v.push_back(k); }
k=0;
for(n=0; n<1000; n++) { k+=xor128()%128; w.push_back(k); }
vector<unsigned int>::iterator p=v.begin();
for(n=0; n<1000; n++){
p=lower_bound( p, v.end(),  w[n]);
k=distance( v.begin(), p  ); 
if(*p==w[n]) { cnt++; cout<<"Hit "<<cnt<<" "<<k<<endl;}
}

}
